Potrzebuję program "Erastotenes"

[wexmop2]

Witam

Nie mam zielonego pojęcia jak napisć program, który by wykonywał algorytm Erastotenesa. Muszę to wykonać na wtorek, a nie wiem jak mam sie za to zabrać bo jest bardzo poplątane.

 

Opis krokowy algorytmu Eratostenesa:

• Wczytaj liczbę n.
• Zmiennej k przypisz wartość 2.
• Jeśli k jest mniejsze bądź równe n, wtedy elementowi tablicy liczby[k] przypisz wartość "prawda", powiększ k o 1 i wykonaj ponownie krok 3. W przeciwnym razie przejdź do nastepnego kroku.
• Zmiennej k przypis zwartość 2.
• Zmiennej m przypisz wartość 2k.
• Jeśli m jest mniejsze bądź równe n,wtedy elementowi tablicy liczby[n] przypisz wartość "fałsz", powiększ m o k i wykonaj ponownie krok 6.
• powiększ k o 1.
• Jeśli k>n, wtedy przejdź do kroku 10. W przeciwnym razie przejdź do nastepnego kroku.
• Jeśli element tablicy liczby[k] ma wartość "prawda" (czyli liczba k nie jest wykreślona), wtedy przejdź do kroku 5. W przeciwnym razie przejdź do kroku 7.
• zmiennej k przypisz wartośc 2.
• Jeśli k jest mniejsze bądź równe n, wtedy przejdź do następnego kroku. W przeciwnym razie zakończ wykonywanie algorytmu.
• Jeśli wartośc elementu tablicy liczby[k] jest "prawdą", wypisz k.
• Powieksz k o 1 i przejdź do kroku 11.

A tutaj jest schemat blokowy:

 

Pomoże ktoś, będę bardzo mocno wdzięczny

[Phoenix_PL]

Zaciekawiłeś mnie. Bierę.

 

W 100% zgodne z OPISEM (nie schematem blokowym, na który nawet nie patrzyłem)

 

 

#include <cstdio>
#include <conio.h>

void write_array(bool* arr, int sizeofarr)
{
    for (int i = 0; i < sizeofarr; i++)
        printf("[%i] - %s\n", i, arr[i] ? "true" : "false");
}

int main()
{
    //1. Wczytaj liczbę n.
    int n;
    puts("Podaj n");
    scanf("%i", &n);

    //2. Zmiennej k przypisz wartość 2.
    int k = 2;

    //deklaracja tablicy, ze względu że nie jest podane ograniczenie wielkości to zrobię to tak
    bool liczby[n+1];

    //3. Jeśli k jest mniejsze bądź równe n, wtedy elementowi tablicy liczby[k] przypisz wartość "prawda",
    //powiększ k o 1 i wykonaj ponownie krok 3. W przeciwnym razie przejdź do nastepnego kroku.
    while (k <= n)
    {
        liczby[k] = true;
        k++;
    }

    //4. Zmiennej k przypis zwartość 2.
    k = 2;

    //5. Zmiennej m przypisz wartość 2k.
    krok_5:
    int m = 2*k;

    //6. Jeśli m jest mniejsze bądź równe n,wtedy elementowi tablicy liczby[n] przypisz wartość "fałsz",
    //powiększ m o k i wykonaj ponownie krok 6.
    while (m <= n)
    {
        liczby[n] = false;
        m += k;
    }

    //7. powiększ k o 1.
    krok_7:
    k++;

    //8. Jeśli k>n, wtedy przejdź do kroku 10. W przeciwnym razie przejdź do nastepnego kroku.
    if (!(k > n)) //jednoznaczne z k <= n, ale robię jak jest w algorytmie
    {
        //9. Jeśli element tablicy liczby[k] ma wartość "prawda" (czyli liczba k nie jest wykreślona), wtedy przejdź do kroku 5.
        //W przeciwnym razie przejdź do kroku 7.
        if (liczby[k] == true)
            goto krok_5;
        else
            goto krok_7;
    }

    //10. zmiennej k przypisz wartośc 2.
    k = 2;

    //11. Jeśli k jest mniejsze bądź równe n, wtedy przejdź do następnego kroku.
    //W przeciwnym razie zakończ wykonywanie algorytmu.
    krok_11:
    if (!(k <= n))
    {  //koniec algorytmu
        printf("\n\nTABLICA:\n"); //dodatkowe wyświetlenie tablicy
        write_array(liczby, n+1); 
        getch();
        return 0;
    }

    //12. Jeśli wartośc elementu tablicy liczby[k] jest "prawdą", wypisz k.
    if (liczby[k] == true) printf("%i\n", k);

    //13. Powieksz k o 1 i przejdź do kroku 11.
    k++;
    goto krok_11;

    return 0;
}

 

 

Mogą być błędy, proszę o ich wskazanie w razie czego.

 

btw; jaki ładny code zrobili...

[sensus12ban]

Witam

Nie mam zielonego pojęcia jak napisć program, który by wykonywał algorytm Erastotenesa. Muszę to wykonać na wtorek, a nie wiem jak mam sie za to zabrać bo jest bardzo poplątane.

 

Opis krokowy algorytmu Eratostenesa:

• Wczytaj liczbę n.
• Zmiennej k przypisz wartość 2.
• Jeśli k jest mniejsze bądź równe n, wtedy elementowi tablicy liczby[k] przypisz wartość "prawda", powiększ k o 1 i wykonaj ponownie krok 3. W przeciwnym razie przejdź do nastepnego kroku.
• Zmiennej k przypis zwartość 2.
• Zmiennej m przypisz wartość 2k.
• Jeśli m jest mniejsze bądź równe n,wtedy elementowi tablicy liczby[n] przypisz wartość "fałsz", powiększ m o k i wykonaj ponownie krok 6.
• powiększ k o 1.
• Jeśli k>n, wtedy przejdź do kroku 10. W przeciwnym razie przejdź do nastepnego kroku.
• Jeśli element tablicy liczby[k] ma wartość "prawda" (czyli liczba k nie jest wykreślona), wtedy przejdź do kroku 5. W przeciwnym razie przejdź do kroku 7.
• zmiennej k przypisz wartośc 2.
• Jeśli k jest mniejsze bądź równe n, wtedy przejdź do następnego kroku. W przeciwnym razie zakończ wykonywanie algorytmu.
• Jeśli wartośc elementu tablicy liczby[k] jest "prawdą", wypisz k.
• Powieksz k o 1 i przejdź do kroku 11.

A tutaj jest schemat blokowy:

 

Pomoże ktoś, będę bardzo mocno wdzięczny

a z ktorym krokiem masz problem? jak masz taki schemat to powinieneś chociaż początek zrobić.

 

..goto...goto...goto Kappa

[Phoenix_PL]

@sensus12ban nie wiem dlaczego ludzie nie używają goto, mimo że nie powoduje to wcale aż takiej nieczytelności kodu a przy pisaniu takich algorytmów niewyobrażalnie pomaga.

 

@Sopelek997 dzięki za bolesne słowa krytyki, muszę wracać do książek.

[Sopelek997]

Napisane w C. C++ jest wolniejsze imo.

 

1. bzdura

2. to nie jest poprawny kod C

3. jeśli ten kod jest na serio to nie pozdrawiam

4. jeśli to "nie wiem dlaczego ludzie nie używają goto, mimo że nie powoduje to wcale aż takiej nieczytelności kodu a przy pisaniu takich algorytmów niewyobrażalnie pomaga." też jest na serio to nie pozdrawiam x 2

4.1. tak, twój kod jest mega nieczytelny

4.2 http://stackoverflow.com/questions/10386152/effect-of-goto-on-c-compiler-optimization

http://stackoverflow.com/questions/17744850/why-the-compiler-cannot-always-optimize-code-that-has-goto?lq=1

 

jedyne użycie goto jakie powinno być tolerowane to wyjście z zagnieżdżonej pętli (da się to też ładnie zrobić używając lambd, ale goto czasem może być lepsze, bo jest krótsze i można zaoszczędzić na wcięciach)

// to ogólnie odnośnie tematu i kodu

1. jeśli ten kod phoenixa jest napisany zgodnie z opisem, to opis jest zły.

2. dobry przykład, że schematy blokowe to syf, a kod napisany na ich podstawie, albo jest syfem, albo się różni na tyle, że schemat blokowy jest tylko utrudnieniem.

3. Jeśli dobrze rozumiem problem to wystarczy to:

#include <iostream>
#include <vector>

int main()
{
    int rozmiar;
    std::cin >> rozmiar;
    std::vector<uint8_t> liczby(rozmiar+1, true);//vector booli to bitset
    liczby[1] = liczby[0] = false;
    for(int i = 2; i*i<=rozmiar; ++i) //zamiast i*i <= rozmiar można przeliczyć integer square root z rozmiar raz na poczatku i do niego porownywac i. Będzie to szybsze.
    {
        if(liczby[i] == false) continue;
        for(int j = i+i; j <= rozmiar; j+=i)
            liczby[j] = false;
    }
    for(int i = 0; i<=rozmiar; ++i) std::cout << i << ' ' << (bool)liczby[i] << '\n';
}

[Nyheq]

@sensus12ban nie wiem dlaczego ludzie nie używają goto, mimo że nie powoduje to wcale aż takiej nieczytelności kodu a przy pisaniu takich algorytmów niewyobrażalnie pomaga.

No i zaciemnia kod, przez co staje się bardzo nieczytelny, a już na pewno nie powinno się dawać newbie kodu z goto.

[wexmop2]

Dzięki za pomoc, ale ja jestem zielony w tych tematach, nie da sie tego jakos bardziej zrozumiale napisac, przejrzyście ?

[Sopelek997]

Dzięki za pomoc, ale ja jestem zielony w tych tematach, nie da sie tego jakos bardziej zrozumiale napisac, przejrzyście ?

jeśli chcesz podążać schematem blokowym to nie

jeśli nie, to masz mój kod wyżej

[Xau]

Można by było użyć std::bitset zamiast std::vector http://www.cplusplus.com/reference/bitset/bitset/

Nie zauważyłem, że rozmiar ma być dynamiczny. Niestety, w standardowej bibliotece nie ma dynamicznego bitseta.

 

Przepisywanie kodu ze schematu blokowego z użyciem goto na pewno jest o wiele wygodniejsze, tylko że taki kod potem do niczego się nie nadaje.